class Solution
{
public:
    unordered_map<int, int> search;
    TreeNode *_bulid(vector<int> &pre, vector<int> &inorder, int &prei, int begini, int endi)
    {
        if (begini > endi)
            return nullptr;
        TreeNode *root = new TreeNode(pre[prei]);
        // 树是肯定存在的，所以不需要判断边界
        int mid = search[pre[prei++]];
        // cout << mid << endl;
        root->left = _bulid(pre, inorder, prei, begini, mid - 1);
        root->right = _bulid(pre, inorder, prei, mid + 1, endi);
        return root;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        int prei = 0;
        for (int i = 0; i < inorder.size(); ++i)
        {
            search.insert({inorder[i], i});
            // cout << search[preorder[i]] << endl;
        }
        return _bulid(preorder, inorder, prei, 0, inorder.size() - 1);
    }
};